package test_package;

import java.util.Stack;

public class Test3 {
    /**
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     */
    public static void main(String[] args) {
        ListNode list = new ListNode(1);
        list.next = new ListNode(2);
        list.next.next = new ListNode(1);
        System.out.println(isPalindrome(list));
        System.out.println(list);
        System.out.println(list.next);
    }

    public static boolean  isPalindrome(ListNode head){
        if (head == null || head.next == null){
            return false;
        }
        ListNode faster = head;
        ListNode slower = head;
        while (faster.next != null && faster.next.next != null){
            slower = slower.next;
            faster = faster.next.next;
        }
        faster = slower.next;
        slower.next = null;
        ListNode temp = null;
        while (faster != null) {
            temp = faster.next;
            faster.next = slower;
            slower = faster;
            faster = temp;
        }
        temp = slower;
        faster = head;
        boolean res = true;
        while (slower != null && faster != null) {
            if (slower.val != faster.val) {
                res = false;
                break;
            }
            slower = slower.next;
            faster = faster.next;
        }
        slower = temp.next;
        temp.next = null;
        while (slower != null) {
            faster = slower.next;
            slower.next = temp;
            temp = slower;
            slower = faster;
        }
        return res;
    }
    public static boolean  isPalindrome1(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
    public static boolean  isPalindrome2(ListNode head){
        if (head == null || head.next == null){
            return false;
        }
        ListNode right = head.next;
        ListNode cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        Stack<ListNode> stack = new Stack<>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
